Hashing Searching Q and A
What is a hashing?
Answer: Hashing is a process of mapping given data to a hash table so that searching of data is quick.
What are the different methods to do hashing?
Answer:
What do you mean by hash collision?
Answer: Hash collision is a situation when two or more data elements hash to same position in the hash table. A hash collision occurs when two or more distinct keys produce the same hash value (i.e., map to the same index) in a hash table. Since hash functions convert arbitrary-sized keys into fixed-size indices, collisions are inevitable when the number of possible keys exceeds the size of the hash table.
How hash collision can be addressed?
Answer: Hash collision can be addressed by using probing methods like linear probing, quadratic probing. In linear probing next slot is created sequentially until an empty slot is found. In Quadratic probing, quadratic function is used to create next slot until an empty slot is found.
What are internal and external searching?
Answer: Internal Searching: The entire dataset fits in main memory (RAM), and searching is performed directly on this in-memory data. Linear search, binary search, hashing, tree-based search are examples of internal searching. External Searching: The dataset is too large to fit in RAM and is stored in secondary storage (disk/SSD). Searching requires fetching data in blocks. B-tree, external hashing, etc. are examples of external searching.
Write time complexities of searching algorithms.
| Searching Algoirthm | Time Complexity |
| Linear Search | O(n) |
| Binary Search | O(log n) |
| Hash Table | O(1) (best Case) or O(n) (worst case) |
| B-tree (disk) | O(logn) |
| Balanced BST | O(logn) |
What is a B-tree?
Answer: A B-Tree is a self-balancing tree data structure designed to maintain sorted data and allow efficient search, insertion, and deletion operations—even for large datasets stored on disk or secondary storage. It generalizes the concept of a Binary Search Tree (BST) but with multiple keys per node and variable child counts, optimizing for systems where disk I/O is the bottleneck.
What do you mean by order of b-tree?
Answer: The order (denoted as m) of a B-Tree defines its branching factor - i.e., the maximum number of children a node can have. It helps to determine:
For a B-Tree of order m:
Keys per Node:
What is an AVL Tree?
Answer: An AVL Tree (named after inventors Adelson-Velsky and Landis) is a type of self-balancing Binary Search Tree (BST) that maintains O(log n) time complexity for search, insert, and delete operations by ensuring the tree remains height-balanced after every modification. It uses a concept of rotation of nodes at the time of insertion (deletion) of a node to maintain balance of tree. In AVL balance factor for each node is defined and it can be -1, -0, and 1 only. That is the height different between any two sub tree cannot be more than 1 or -1.
What is an Huffman's algorithm?
Answer: Huffmans algorithm is a greedy algorithm used for lossless data compression. It used concept of binary tree. It constructs a variable-length prefix-free code (known as a Huffman code) that minimizes the expected number of bits needed to represent symbols (e.g., characters in a file). The most frequent symbols get the shortest codes, while rare symbols get longer ones. A binary tree is created to represent or code given text using values (0 and 1). Same tree is used to decode the given text also.
what is an expression tree?
Answer: An expression tree is a binary tree where: